package 栈和队列;

import java.util.Stack;

/**
 * 逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）
 * 一个表达式E的后缀形式可以如下定义：
 * （1）如果E是一个变量或常量，则E的后缀式是E本身。
 * （2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为E1和E2的后缀式。
 * （3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
 * 如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
 * (a+b)*c-(a+b)/e的后缀表达式为：
 * (a+b)*c-(a+b)/e
 * →((a+b)*c)((a+b)/e)-
 * →((a+b)c*)((a+b)e/)-
 * →(ab+c*)(ab+e/)-\
 * →ab+c*ab+e/-
 */
public class EvalRPN {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<tokens.length;i++){
            String s = tokens[i];
            if(s.equals("+")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2+num1);
            }else if(s.equals("-")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2-num1);
            }else if(s.equals("*")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2*num1);
            }else if(s.equals("/")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num2/num1);
            }else{
                int num = Integer.parseInt(s);
                stack.push(num);
            }
        }
        return stack.pop();
    }
}
